Definition

Solution where one player cannot improve his outcome by altering his decision unilaterally, known as Nash equilibrium solution or Nash solution.

Proposition

Consider a game Γ:{N,{si},{ui(⋅)}}\Gamma: \{N, \{s_i\}, \{u_i(\cdot)\}\}. It admits a Nash equilibrium (NE) if ∀i∈N\forall i \in N,

  1. sis_i: nonempty, convex, compact subset of ℝm\mathbb{R}^m
  2. ui(⋅)u_i(\cdot): continuous in (S1...SN)(S_1...S_N) and concave in si∈Sis_i \in S_i.

Pure strategies

Theorem (optimal strategies and value)

If a two-player zero-sum game has a value vv, and if sI∗s_I^* and sII∗s_{II}^* are optimal strategies of the two players, then s∗=(sI∗,sII∗)s^* = (s_I^*, s_{II}^*) is an equilibrium with payoff (v,−v)(v, -v).

(under convention of p1 maximizer, p2 minimizer)

pure strategy in bimatrix game

Theorem (equilibrium and value)

If s∗=(sI∗,sII∗)s^* = (s_I^*, s_{II}^*) is an equilibrium of a two-player zero-sum game, then the game has a value v=u(sI∗,sII∗)v = u(s_I^*, s_{II}^*), and the strategies sI∗s_I^* and sII∗s_{II}^* are optimal strategies.

Mixed strategies

Definition (in mixed strategies)

(pi∗,p−i∗)(p_i^*, p_{-i}^*) is a Nash equilibrium in mixed strategies if

u~i(pi∗,p−i∗)≥u~i(pi,p−i∗)\tilde{u}_i(p_i^*, p_{-i}^*) \geq \tilde{u}_i(p_i, p_{-i}^*)

for all admissible pi∈Δ(Xi)p_i \in \Delta(X_i) and for all i∈Ni \in N, which is equivalent to

pi∗∈arg⁡maxpi∈Δ(Xi)⁡u~i(pi,p−i∗)∀ip_i^* \in \arg\max_{p_i \in \Delta(X_i)} \tilde{u}_i(p_i, p_{-i}^*) \quad\forall i

Note sometimes pi∈Δ~(Xi)⊂Δ(Xi)p_i \in \tilde{\Delta}(X_i) \subset \Delta(X_i)

mixed strategy in bimatrix game

Theorem (Nash 1950b, 1951)

Every game in strategic-form GG, with a finite number of players and in which every player has a finite number of pure strategies, has an equilibrium in mixed strategies.

Theorem (equilibrium of ε\varepsilon-perturbed game)

Every (finite) ε-perturbed game has an equilibrium; i.e. there exists a mixed strategy vector σ∗=(σi∗)i∈N\sigma^* = (\sigma_i^*)_{i \in N} satisfying σi∗∈Σi(εi)\sigma_i^* \in \Sigma_i (\varepsilon_i) for each player i∈Ni \in N, and

Ui(σ∗)≥Ui(σi,σ−i∗),∀i∈N, ∀σi∈Σi(εi)U_i(\sigma^*) \geq U_i(\sigma_i, \sigma_{-i}^*), \quad \forall i \in N,\ \forall \sigma_i \in \Sigma_i(\varepsilon_i)

Corollary (perfect equilibrium as Nash equilibrium)

Every perfect equilibrium of finite strategic-form game is a Nash equilibrium.

Notes

References

  1. Nash Jr, J. F. (1950). Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1), 48-49. DOI:10.1073/pnas.36.1.48. https://pmc.ncbi.nlm.nih.gov/articles/PMC1063129/pdf/pnas01550-0057.pdf
  2. Nash J. F. (1951) Noncooperative games. Annals of Mathematics, 54, 289–95.
  3. https://bpb-us-e1.wpmucdn.com/wp.nyu.edu/dist/5/2123/files/2019/12/Lecture-3-Scribe.pdf
  4. M. Maschler, E. Solan, and Shmuel Zamir, Game Theory, Cambridge University Press, 2013, pp. 115, 151, 264.
  5. https://en.wikipedia.org/wiki/Subgame_perfect_equilibrium
  6. Myerson, R. B. (1978). Refinements of the Nash equilibrium concept. International Journal of Game Theory, 7(2), 73–80. https://doi.org/10.1007/BF01753236
  7. Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4(1), 25–55. https://doi.org/10.1007/BF01766400
  8. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The complexity of computing a Nash equilibrium,” Commun. ACM, vol. 52, no. 2, pp. 89–97, Feb. 2009, doi: 10.1145/1461928.1461951.